As data transfer becomes more and more complex, the numbers of the messages which need to be transferred across a network from one location to another, or one area of a computing device to another, has grown remarkably. Accordingly, any system or subcomponent thereof which allows for ease of routing messages from any of a large number of inputs to any particular one of a large number of outputs is important. The invention described herein allows for the routing of such messages with very little overhead, at high speed.
The invention herein employs a return network, is capable of using different kinds of switches in the switching network, may operate in a broadcast mode, may reduce the number of switches necessary by using a Clos network or by reliance on busses and controllers, and uses a self-routing algorithm, eliminating the need for preprocessing overhead.
Self-routing algorithms use information contained in the message itself to route the message at the switch level to the desired location.
Prior self-routing algorithms such as the one described in the 1990 IEEE (Vol. 78, No. 1), entitled "Fast Packet Switch Architectures for Broad-Band Integrated Services Digital Networks", by Tobagi, do not indicate how these algorithms can actually operate, and do not describe how their operation can be accomplished when using a Clos-type network.
Clos networks are preferred for larger networks because they reduce the number of switches necessary to accomplish a N.times.N message switching system to a much smaller number than N.sup.2. See, for example, U.S. Pat. No. 4,696,000, issued to Payne, which refers to the Clos network and rearrangeable networks.
The invention described herein simplifies all these ideas.
The switches may be arranged in a standard crossbar network for small scale implementations, a Clos network or a variation of a Clos network using busses, and the types of switches and routings, dependent on the switch type used, may also vary depending on the implementation. As described in the detailed description, a preferred implementation employs a return network for all blocked messages that wish to address the same output node and returns them to the source or sending node. Due to the nature of the routing system itself and the construction of the switching network, essentially no overhead or preprocessing is required to route messages through the system described from the input nodes to the output nodes.